#include "stdafx.h"
#include "TestUtils.h"
#include "Graph.h"
#include "Group.h"
#include "Vertex.h"
#include "VertexSet.h"
#include "SwitchingAlgorithmTests.h"
#include "Helpers.h"
#include <cstdlib>

using namespace std;

TestUtils::TestResult TestIsLegalForInterchangeableThatCannotBeReturnedOrReplaced()
{
	VertexDirectory::Clear();
	Graph graph(400);
	graph = TestUtils::CreateGraph4On2(graph);

	Group group0(0), group1(1);
	bool name1[] = {1,1,0,0};
	bool name2[] = {0,1,0,1};
	int n = 4;
	Vertex *vertex1 = VertexDirectory::GetStaticCopyVertex(Vertex::GetNameFromArray(name1,n));
	Vertex *vertex2 = VertexDirectory::GetStaticCopyVertex(Vertex::GetNameFromArray(name2,n));
	
	graph.RemoveVertex(vertex1);
	group0.InsertNewVertex(vertex1);
	// Vertex2 can replace vertex1
	Vertex::CreateInterchangeableLink(vertex1, vertex2);
	// Not anymore, so now vertex1 cannot be replaced
	vertex1->RemoveAllReplacements();
	
	if (TestUtils::VerifyIsTrue(!group1.IsLegalToAdd(vertex1, true),"Can add vertex with no replacements to a group") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}
	
	return TestUtils::TestPassed;
}

TestUtils::TestResult TestIsLegalForInterchangeableSetThatCannotBeReturnedOrReplaced()
{
	VertexDirectory::Clear();
	Graph graph(400);
	graph = TestUtils::CreateGraph4On2(graph);

	Group group0(0);
	bool name1[] = {0,1,1,0};
	bool name2[] = {1,0,0,1};
	bool name3[] = {1,0,1,0};
	bool name4[] = {0,1,0,1};
	int n = 4;
	Vertex *vertex1 = VertexDirectory::GetStaticCopyVertex(Vertex::GetNameFromArray(name1,n));
	Vertex *vertex2 = VertexDirectory::GetStaticCopyVertex(Vertex::GetNameFromArray(name2,n));
	Vertex *vertex3 = VertexDirectory::GetStaticCopyVertex(Vertex::GetNameFromArray(name3,n));
	Vertex *vertex4 = VertexDirectory::GetStaticCopyVertex(Vertex::GetNameFromArray(name4,n));

	VertexSet *set1 = new VertexSet(vertex1, vertex2);
	VertexSet *set2 = new VertexSet(vertex3, vertex4);
	
	graph.RemoveVertexSet(set1);
	group0.InsertNewVertexCouple(set1);
	// set2 can replace set1
	VertexSet::CreateInterchangeableLink(set1, set2);

	VertexDirectory::AddVertexSet(set1);
	VertexDirectory::AddVertexSet(set2);
	// Not anymore, so now set1 cannot be replaced
	set1->RemoveAllReplacements();

	
	if (TestUtils::VerifyIsTrue(!group0.IsLegalToAdd(set1, true),"Can add vertex set with no replacements to a group") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}
	
	return TestUtils::TestPassed;
}

TestUtils::TestResult TestIsLegalForReplacementSetThatIsRequiredForInterchangeableSet()
{
	TestUtils::CreateVertexDirectory(5,2);
	map<vector<bool>, Vertex*>* vertices = VertexDirectory::GetStaticCopyVertices();
    VertexDirectory::ClearAllVertexSets();
	Graph* graph = TestUtils::CreateGraphFromDirectory(vertices, NULL);

	Group group0(0);
	bool name1[] = {0,1,1,0,0};
	bool name5[] = {1,0,0,1,0};


	bool name2[] = {0,1,0,1,0};
	bool name4[] = {0,1,0,0,1};
	
	bool name3[] = {1,0,1,0,0};
	int n = 5;
	Vertex *vertex1 = VertexDirectory::GetVertexFromDirectory(Vertex::GetNameFromArray(name1,n), NULL);
	Vertex *vertex2 = VertexDirectory::GetVertexFromDirectory(Vertex::GetNameFromArray(name2,n), NULL);
	Vertex *vertex3 = VertexDirectory::GetVertexFromDirectory(Vertex::GetNameFromArray(name3,n), NULL);
	Vertex *vertex4 = VertexDirectory::GetVertexFromDirectory(Vertex::GetNameFromArray(name4,n), NULL);
	Vertex *vertex5 = VertexDirectory::GetVertexFromDirectory(Vertex::GetNameFromArray(name5,n), NULL);

	VertexSet *set1 = new VertexSet(vertex1,vertex5);
	VertexSet *set2 = new VertexSet(vertex2,vertex4);
		
	graph->RemoveVertexSet(set1);
	group0.InsertNewVertexCouple(set1);
	// Vertex2 can replace vertex1
	VertexSet::CreateInterchangeableLink(set1,set2);
	// now put vertex1 back in the graph
	group0.RemoveVertexSet(set1);
	graph->InsertVertexSet(set1);
	
	// And add vertex3 to group
	group0.InsertNewVertex(vertex3);

	VertexDirectory::AddVertexSet(set1);
	VertexDirectory::AddVertexSet(set2);

	
	// Vertex3 and Vertex2 aren't neighbours, but Vertex1 and Vertex3 are so if we put Vertex2 in the group
	// we can't return vertex1 to it and it has no more replacements
	if (TestUtils::VerifyIsTrue(!group0.IsLegalToAdd(set2, true),"Can add replacement vertex set to a group leaving its interchangeable vertex set stuck") 
		== TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	// Make sure we left the vertices where they are supposed to be
	if (TestUtils::VerifyIsTrue(vertex1->IsInGraph(), "Vertex1 is supposed to be in graph but it doesn't think so") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(vertex1->GetContainer() != &group0, "Vertex1 thinks it is in group0") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}
	if (TestUtils::VerifyIsTrue(vertex4->IsInGraph(), "Vertex1 is supposed to be in graph but it doesn't think so") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(vertex4->GetContainer() != &group0, "Vertex1 thinks it is in group0") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(vertex2->IsInGraph(), "Vertex2 is supposed to be in graph but it doesn't think so") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(vertex2->GetContainer() != &group0, "Vertex2 thinks it is in group0") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}
	if (TestUtils::VerifyIsTrue(vertex5->GetContainer() != &group0, "Vertex2 thinks it is in group0") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(!vertex3->IsInGraph(), "Vertex3  is  not supposed to be in graph but it doesn't think so") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(vertex3->GetContainer() == &group0, "Vertex3 thinks it is not in group0") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	return TestUtils::TestPassed;
}

TestUtils::TestResult TestIsLegalForReplacementThatIsRequiredForInterchangeable()
{
	VertexDirectory::Clear();
	Graph graph(400);
	graph = TestUtils::CreateGraph4On2(graph);

	Group group0(0);
	bool name1[] = {0,1,1,0};
	bool name2[] = {0,1,0,1};
	bool name3[] = {1,0,1,0};
	int n = 4;
	Vertex *vertex1 = VertexDirectory::GetStaticCopyVertex(Vertex::GetNameFromArray(name1,n));
	Vertex *vertex2 = VertexDirectory::GetStaticCopyVertex(Vertex::GetNameFromArray(name2,n));
	Vertex *vertex3 = VertexDirectory::GetStaticCopyVertex(Vertex::GetNameFromArray(name3,n));
		
	graph.RemoveVertex(vertex1);
	group0.InsertNewVertex(vertex1);
	// Vertex2 can replace vertex1
	Vertex::CreateInterchangeableLink(vertex1,vertex2);
	// now put vertex1 back in the graph
	group0.RemoveVertex(vertex1);
	graph.InsertVertex(vertex1);
	
	// And add vertex3 to group
	group0.InsertNewVertex(vertex3);
	
	// Vertex3 and Vertex2 aren't neighbours, but Vertex1 and Vertex3 are so if we put Vertex2 in the group
	// we can't return vertex1 to it and it has no more replacements
	if (TestUtils::VerifyIsTrue(!group0.IsLegalToAdd(vertex2, true),"Can add replacement vertex to a group leaving its interchangeable vertex stuck") 
		== TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	// Make sure we left the vertices where they are supposed to be
	if (TestUtils::VerifyIsTrue(vertex1->IsInGraph(), "Vertex1 is supposed to be in graph but it doesn't think so") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(vertex1->GetContainer() != &group0, "Vertex1 thinks it is in group0") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(vertex2->IsInGraph(), "Vertex2 is supposed to be in graph but it doesn't think so") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(vertex2->GetContainer() != &group0, "Vertex2 thinks it is in group0") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(!vertex3->IsInGraph(), "Vertex3  is  not supposed to be in graph but it doesn't think so") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(vertex3->GetContainer() == &group0, "Vertex3 thinks it is not in group0") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	return TestUtils::TestPassed;
}

TestUtils::TestResult TestIsLegalForLastReplacementThatIsNotRequiredForInterchangeable()
{
	VertexDirectory::Clear();
	Graph graph(400);
	graph = TestUtils::CreateGraph4On2(graph);

	Group group0(0), group1(1);
	bool name1[] = {0,1,1,0};
	bool name2[] = {0,1,0,1};
	bool name3[] = {1,0,1,0};
	int n = 4;
	Vertex *vertex1 = VertexDirectory::GetStaticCopyVertex(Vertex::GetNameFromArray(name1,n));
	Vertex *vertex2 = VertexDirectory::GetStaticCopyVertex(Vertex::GetNameFromArray(name2,n));
	Vertex *vertex3 = VertexDirectory::GetStaticCopyVertex(Vertex::GetNameFromArray(name3,n));
		
	graph.RemoveVertex(vertex1);
	group0.InsertNewVertex(vertex1);
	// Vertex2 can replace vertex1
	Vertex::CreateInterchangeableLink(vertex1,vertex2);
	// now put vertex1 back in the graph
	group0.RemoveVertex(vertex1);
	graph.InsertVertex(vertex1);
	
	// And add vertex3 to group1
	graph.RemoveVertex(vertex3);
	group1.InsertNewVertex(vertex3);
	
	// Adding vertex2 to group1 will result in vertex1 having no replacements, but it can return to group0 so no problem
	if (TestUtils::VerifyIsTrue(group1.IsLegalToAdd(vertex2, true),"Cannot add last replacement vertex to a group when interchangeable can return to original") 
		== TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	// Make sure we left the vertices where they are supposed to be
	if (TestUtils::VerifyIsTrue(vertex1->IsInGraph(), "Vertex1 is supposed to be in graph but it doesn't think so") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(vertex1->GetContainer() != &group0, "Vertex1 thinks it is in group0") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(vertex2->IsInGraph(), "Vertex2 is supposed to be in graph but it doesn't think so") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(vertex2->GetContainer() != &group0, "Vertex2 thinks it is in group0") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(!vertex3->IsInGraph(), "Vertex3  is  not supposed to be in graph but it doesn't think so") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(vertex3->GetContainer() == &group1, "Vertex3 thinks it is not in group1") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	return TestUtils::TestPassed;
}

TestUtils::TestResult TestIsLegalForLastReplacementThatIsNotRequiredForInterchangeableSet()
{
	TestUtils::CreateVertexDirectory(5,2);
	map<vector<bool>, Vertex*>* vertices = VertexDirectory::GetStaticCopyVertices();
	VertexDirectory* dir = new VertexDirectory(vertices);
	Graph* graph = TestUtils::CreateGraphFromDirectory(vertices, dir);

	Group group0(0), group1(1);
	bool name1[] = {0,1,1,0,0};
	bool name5[] = {1,0,0,1,0};


	bool name2[] = {0,1,0,1,0};
	bool name4[] = {0,1,0,0,1};
	
	bool name3[] = {1,0,1,0,0};
	int n = 5;
	Vertex *vertex1 = VertexDirectory::GetVertexFromDirectory(Vertex::GetNameFromArray(name1,n), dir);
	Vertex *vertex2 = VertexDirectory::GetVertexFromDirectory(Vertex::GetNameFromArray(name2,n), dir);
	Vertex *vertex3 = VertexDirectory::GetVertexFromDirectory(Vertex::GetNameFromArray(name3,n), dir);
	Vertex *vertex4 = VertexDirectory::GetVertexFromDirectory(Vertex::GetNameFromArray(name4,n), dir);
	Vertex *vertex5 = VertexDirectory::GetVertexFromDirectory(Vertex::GetNameFromArray(name5,n), dir);

	VertexSet *set1 = new VertexSet(vertex1,vertex5);
	VertexSet *set2 = new VertexSet(vertex2,vertex4);
		
	graph->RemoveVertexSet(set1);
	group0.InsertNewVertexCouple(set1);
	// Vertex2 can replace vertex1
	VertexSet::CreateInterchangeableLink(set1,set2);
	// now put vertex1 back in the graph
	group0.RemoveVertexSet(set1);
	graph->InsertVertexSet(set1);

	VertexDirectory::ClearAllVertexSets();
	VertexDirectory::AddVertexSet(set1);
	VertexDirectory::AddVertexSet(set2);
	// Adding set2 to group1 will result in vertex1 having no replacements, but it can return to group0 so no problem
	if (TestUtils::VerifyIsTrue(group1.IsLegalToAdd(set2, true),"Cannot add last replacement vertex to a group when interchangeable can return to original") 
		== TestUtils::TestFailed)
	{
		delete dir;
		return TestUtils::TestFailed;
	}

	list<Group*> groups;
	groups.push_back(&group0);
	groups.push_back(&group1);
	set<int> groupNames;
	groupNames.insert(0);
	groupNames.insert(1);
	// Make sure we left the vertices where they are supposed to be
	// check that the directory was updated correctly: All vertices in the graph appear in the graph. All vertices
	// in the group point to the right group.
	if (Algorithms::ValidateVertexDirectoryState(graph, groups, groupNames) == false)
	{
		delete dir;
		return TestUtils::TestFailed;
	}
	
	delete dir;
	return TestUtils::TestPassed;
}


TestUtils::TestResult TestIsLegalForVertexThatRuinsReplacements()
{
	VertexDirectory::Clear();
	Graph graph(400);
	graph = TestUtils::CreateGraph4On2(graph);

	Group group0(0);
	bool name1[] = {0,1,1,0};
	bool name2[] = {1,0,0,1};
	bool name3[] = {1,0,1,0};
	bool name4[] = {0,1,0,1};
	int n = 4;
	Vertex *vertex1 = VertexDirectory::GetStaticCopyVertex(Vertex::GetNameFromArray(name1,n));
	Vertex *vertex2 = VertexDirectory::GetStaticCopyVertex(Vertex::GetNameFromArray(name2,n));
	Vertex *vertex3 = VertexDirectory::GetStaticCopyVertex(Vertex::GetNameFromArray(name3,n));
	Vertex *vertex4 = VertexDirectory::GetStaticCopyVertex(Vertex::GetNameFromArray(name4,n));
		
	graph.RemoveVertex(vertex1);
	group0.InsertNewVertex(vertex1);
	// Vertex2 can replace vertex1
	Vertex::CreateInterchangeableLink(vertex1,vertex2);
	// now put vertex1 back in the graph
	group0.RemoveVertex(vertex1);
	graph.InsertVertex(vertex1);
	
	// And add vertex3 to group0
	graph.RemoveVertex(vertex3);
	group0.InsertNewVertex(vertex3);
	
	// If we add vertex4 to group0, then vertex1 can't return to it's original group and it's replacements can't replace it
	// it should be illegal
	if (TestUtils::VerifyIsTrue(!group0.IsLegalToAdd(vertex4,true),"Can add vertex to group if it creates a vertex that is stuck") 
		== TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	// Make sure we left the vertices where they are supposed to be
	if (TestUtils::VerifyIsTrue(vertex1->IsInGraph(), "Vertex1 is supposed to be in graph but it doesn't think so") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(vertex1->GetContainer() != &group0, "Vertex1 thinks it is in group0") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(vertex2->IsInGraph(), "Vertex2 is supposed to be in graph but it doesn't think so") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(vertex2->GetContainer() != &group0, "Vertex2 thinks it is in group0") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(!vertex3->IsInGraph(), "Vertex3  is  not supposed to be in graph but it doesn't think so") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(vertex3->GetContainer() == &group0, "Vertex3 thinks it is not in group0") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(vertex4->IsInGraph(), "Vertex4 is supposed to be in graph but it doesn't think so") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(vertex4->GetContainer() != &group0, "Vertex4 thinks it is in group0") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	return TestUtils::TestPassed;
}


TestUtils::TestResult TestIsLegalForVertexSetThatRuinsReplacements()
{
	TestUtils::CreateVertexDirectory(5,2);
	map<vector<bool>, Vertex*>* vertices = VertexDirectory::GetStaticCopyVertices();
	Graph* graph = TestUtils::CreateGraphFromDirectory(vertices, NULL);

	Group group0(0), group1(1);
	bool name1[] = {0,1,1,0,0};
	bool name5[] = {1,0,0,1,0};


	bool name2[] = {0,1,0,1,0};
	bool name4[] = {0,0,1,0,1};
	
	bool name3[] = {1,0,1,0,0}; //neighbours with name5

	bool name6[] = {0,1,0,0,1}; // neighbours with 2
	bool name7[] = {1,0,0,1,0};
	
	int n = 5;
	Vertex *vertex1 = VertexDirectory::GetVertexFromDirectory(Vertex::GetNameFromArray(name1,n), NULL);
	Vertex *vertex2 = VertexDirectory::GetVertexFromDirectory(Vertex::GetNameFromArray(name2,n), NULL);
	Vertex *vertex3 = VertexDirectory::GetVertexFromDirectory(Vertex::GetNameFromArray(name3,n), NULL);
	Vertex *vertex4 = VertexDirectory::GetVertexFromDirectory(Vertex::GetNameFromArray(name4,n), NULL);
	Vertex *vertex5 = VertexDirectory::GetVertexFromDirectory(Vertex::GetNameFromArray(name5,n), NULL);
	Vertex *vertex6 = VertexDirectory::GetVertexFromDirectory(Vertex::GetNameFromArray(name6,n), NULL);
	Vertex *vertex7 = VertexDirectory::GetVertexFromDirectory(Vertex::GetNameFromArray(name7,n), NULL);

	VertexSet *set1 = new VertexSet(vertex1,vertex5);
	VertexSet *set2 = new VertexSet(vertex2,vertex4);
	VertexSet *set3 = new VertexSet(vertex6,vertex7);
		
	graph->RemoveVertexSet(set1);
	group0.InsertNewVertexCouple(set1);
	// Vertex2 can replace vertex1
	VertexSet::CreateInterchangeableLink(set1,set2);
	// now put vertex1 back in the graph
	group0.RemoveVertexSet(set1);
	graph->InsertVertexSet(set1);

	// And add vertex3 to group0
	graph->RemoveVertex(vertex3);
	group0.InsertNewVertex(vertex3);


	VertexDirectory::ClearAllVertexSets();
	VertexDirectory::AddVertexSet(set1);
	VertexDirectory::AddVertexSet(set2);
	VertexDirectory::AddVertexSet(set3);

	// If we add set3 to group0, then vertex1 can't return to it's original group and it's replacements can't replace it
	// it should be illegal
	if (TestUtils::VerifyIsTrue(!group0.IsLegalToAdd(set3,true),"Can add vertex set to group if it creates a vertex that is stuck") 
		== TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	// Make sure we left the vertices where they are supposed to be
		// check that the directory was updated correctly: All vertices in the graph appear in the graph. All vertices
	// in the group point to the right group.
	if (Algorithms::ValidateVertexDirectoryState(graph, &group0) == false)
	{
		return TestUtils::TestFailed;
	}

	return TestUtils::TestPassed;
}

TestUtils::TestResult TestIsLegalForVertexWithSingleReplacementFor2Vertices()
{
	VertexDirectory::Clear();
	Graph graph(400);
	graph = TestUtils::CreateGraph4On2(graph);

	Group group0(0);
	bool name1[] = {0,0,1,1};
	bool name2[] = {1,1,0,0};
	bool name3[] = {1,0,1,0};
	bool name4[] = {0,1,0,1};
	bool name5[] = {1,0,0,1};
	bool name6[] = {0,1,1,0};
	int n = 4;
	Vertex *vertex1 = VertexDirectory::GetStaticCopyVertex(Vertex::GetNameFromArray(name1,n));
	Vertex *vertex2 = VertexDirectory::GetStaticCopyVertex(Vertex::GetNameFromArray(name2,n));
	Vertex *vertex3 = VertexDirectory::GetStaticCopyVertex(Vertex::GetNameFromArray(name3,n));
	Vertex *vertex4 = VertexDirectory::GetStaticCopyVertex(Vertex::GetNameFromArray(name4,n));
	Vertex *vertex5 = VertexDirectory::GetStaticCopyVertex(Vertex::GetNameFromArray(name5,n));
	Vertex *vertex6 = VertexDirectory::GetStaticCopyVertex(Vertex::GetNameFromArray(name6,n));

	// Put vertex1 (0011) + vertex2 (1100) in group0
	graph.RemoveVertex(vertex1); group0.InsertNewVertex(vertex1);
	graph.RemoveVertex(vertex2); group0.InsertNewVertex(vertex2);

	// Set 1010 and 0110 as replacements for 0011
	Vertex::CreateInterchangeableLink(vertex1,vertex3);
	Vertex::CreateInterchangeableLink(vertex1,vertex6);

	// Set 0101 and 0110 as replacements for 1100
	Vertex::CreateInterchangeableLink(vertex2,vertex4);
	Vertex::CreateInterchangeableLink(vertex2,vertex6);

	// Remove 0011 and 1100 from group and put them in graph
	group0.RemoveVertex(vertex1); graph.InsertVertex(vertex1);
	group0.RemoveVertex(vertex2); graph.InsertVertex(vertex2);

	// Now we try to add 1001. It has no neighbours in the group, but if we use it
	// then both 0011 and 1100 have to use 0110 as the replacement and this is illegal
	// If we add vertex4 to group0, then vertex1 can't return to it's original group and it's replacements can't replace it
	// it should be illegal
	if (TestUtils::VerifyIsTrue(!group0.IsLegalToAdd(vertex5, true),"Can add vertex to group if it creates a vertex that is stuck") 
		== TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	// Make sure we left the vertices where they are supposed to be
	if (TestUtils::VerifyIsTrue(vertex1->IsInGraph(), "Vertex1 is supposed to be in graph but it doesn't think so") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(vertex1->GetContainer() != &group0, "Vertex1 thinks it is in group0") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(vertex2->IsInGraph(), "Vertex2 is supposed to be in graph but it doesn't think so") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(vertex2->GetContainer() != &group0, "Vertex2 thinks it is in group0") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(vertex3->IsInGraph(), "Vertex3  is in graph but it doesn't think so") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(vertex3->GetContainer() != &group0, "Vertex3 thinks it is in group0") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(vertex4->IsInGraph(), "Vertex4 is supposed to be in graph but it doesn't think so") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(vertex4->GetContainer() != &group0, "Vertex4 thinks it is in group0") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(vertex5->IsInGraph(), "Vertex5 is supposed to be in graph but it doesn't think so") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(vertex5->GetContainer() != &group0, "Vertex5 thinks it is in group0") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(vertex6->IsInGraph(), "Vertex6 is supposed to be in graph but it doesn't think so") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(vertex6->GetContainer() != &group0, "Vertex6 thinks it is in group0") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	return TestUtils::TestPassed;
}

TestUtils::TestResult TestIsLegalForVertexSetWithSingleReplacemenSetFor2Vertices()
{
	// Scenario: 2 sets both have the same replacement set
	// their original group has neighbours in it and they can't return
	// They each have 2 replacements, one is common to both
	// We try and add a vertex set that is neighbours with both the replacements
	// that aren't common to both
	// This should be illegal
	TestUtils::CreateVertexDirectory(6,3);
	map<vector<bool>, Vertex*>* vertices = VertexDirectory::GetStaticCopyVertices();
	Graph* graph = TestUtils::CreateGraphFromDirectory(vertices, NULL);

	Group group0(0), group1(1);
	// set1
	bool name1[] = {0,1,1,0,0,1};
	bool name5[] = {1,0,0,1,0,1};
		
	// set2
	bool name2[] = {1,0,1,0,1,0};
	bool name4[] = {0,1,0,1,1,0};
	
				   
	bool name3[] = {1,0,1,0,0,1}; //neighbours with set1+set2

	bool name6[] = {1,0,1,0,1,0}; // set3 replaces 1+2
	bool name7[] = {1,1,0,1,0,0};

	bool name8[] = {1,1,0,0,0,1}; // set4 replaces 1, neigbours with 3
	bool name9[] = {1,1,0,1,0,0}; 
	
	bool name10[] = {0,1,0,0,1,1}; // set5 replaces 2, neigbours with 3
	bool name11[] = {1,0,0,1,0,1}; 

	bool name12[] = {1,1,1,0,0,0}; // set6, neighbours with set4+set5
	bool name13[] = {0,1,0,1,0,1};
	int n = 6;
	Vertex *vertex1 = VertexDirectory::GetVertexFromDirectory(Vertex::GetNameFromArray(name1,n), NULL);
	Vertex *vertex2 = VertexDirectory::GetVertexFromDirectory(Vertex::GetNameFromArray(name2,n), NULL);
	Vertex *vertex3 = VertexDirectory::GetVertexFromDirectory(Vertex::GetNameFromArray(name3,n), NULL);
	Vertex *vertex4 = VertexDirectory::GetVertexFromDirectory(Vertex::GetNameFromArray(name4,n), NULL);
	Vertex *vertex5 = VertexDirectory::GetVertexFromDirectory(Vertex::GetNameFromArray(name5,n), NULL);
	Vertex *vertex6 = VertexDirectory::GetVertexFromDirectory(Vertex::GetNameFromArray(name6,n), NULL);
	Vertex *vertex7 = VertexDirectory::GetVertexFromDirectory(Vertex::GetNameFromArray(name7,n), NULL);
	Vertex *vertex8 = VertexDirectory::GetVertexFromDirectory(Vertex::GetNameFromArray(name8,n), NULL);
	Vertex *vertex9 = VertexDirectory::GetVertexFromDirectory(Vertex::GetNameFromArray(name9,n), NULL);
	Vertex *vertex10 = VertexDirectory::GetVertexFromDirectory(Vertex::GetNameFromArray(name10,n), NULL);
	Vertex *vertex11 = VertexDirectory::GetVertexFromDirectory(Vertex::GetNameFromArray(name11,n), NULL);
	Vertex *vertex12 = VertexDirectory::GetVertexFromDirectory(Vertex::GetNameFromArray(name12,n), NULL);
	Vertex *vertex13 = VertexDirectory::GetVertexFromDirectory(Vertex::GetNameFromArray(name13,n), NULL);

	VertexSet *set1 = new VertexSet(vertex1,vertex5);
	VertexSet *set2 = new VertexSet(vertex2,vertex4);
	VertexSet *set3 = new VertexSet(vertex6,vertex7);
	VertexSet *set4 = new VertexSet(vertex8,vertex9);
	VertexSet *set5 = new VertexSet(vertex10,vertex11);
	VertexSet *set6 = new VertexSet(vertex12,vertex13);
		
	graph->RemoveVertexSet(set1);
	group0.InsertNewVertexCouple(set1);
	graph->RemoveVertexSet(set2);
	group0.InsertNewVertexCouple(set2);
	// Vertex2 can replace vertex1
	VertexSet::CreateInterchangeableLink(set1,set3);
	VertexSet::CreateInterchangeableLink(set1,set4);
	
	VertexSet::CreateInterchangeableLink(set2,set3);
	VertexSet::CreateInterchangeableLink(set2,set5);

	// now put vertex1 back in the graph
	group0.RemoveVertexSet(set1);
	graph->InsertVertexSet(set1);

	group0.RemoveVertexSet(set2);
	graph->InsertVertexSet(set2);

	// And add vertex3 to group0
	graph->RemoveVertex(vertex3);
	group0.InsertNewVertex(vertex3);

	VertexDirectory::ClearAllVertexSets();
	VertexDirectory::AddVertexSet(set1);
	VertexDirectory::AddVertexSet(set2);
	VertexDirectory::AddVertexSet(set3);
	VertexDirectory::AddVertexSet(set5);
	VertexDirectory::AddVertexSet(set4);


	if (TestUtils::VerifyIsTrue(!group0.IsLegalToAdd(set6, true),"Can add vertex set to group if it creates a vertex that is stuck") 
		== TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	// Make sure we left the vertices where they are supposed to be
	// check that the directory was updated correctly: All vertices in the graph appear in the graph. All vertices
	// in the group point to the right group.
	if (Algorithms::ValidateVertexDirectoryState(graph, &group0) == false)
	{
		return TestUtils::TestFailed;
	}

	return TestUtils::TestPassed;

}


TestUtils::TestResult TestReplace()
{
	VertexDirectory::Clear();
	Graph graph(400);
	graph = TestUtils::CreateGraph4On2(graph);

	Group group0(0);
	bool name1[] = {0,1,1,0};
	bool name2[] = {1,0,0,1};
	bool name3[] = {1,0,1,0};
	bool name4[] = {0,1,0,1};
	int n = 4;
	Vertex *vertex1 = VertexDirectory::GetStaticCopyVertex(Vertex::GetNameFromArray(name1,n));
	Vertex *vertex2 = VertexDirectory::GetStaticCopyVertex(Vertex::GetNameFromArray(name2,n));
	Vertex *vertex3 = VertexDirectory::GetStaticCopyVertex(Vertex::GetNameFromArray(name3,n));
	Vertex *vertex4 = VertexDirectory::GetStaticCopyVertex(Vertex::GetNameFromArray(name4,n));
		
	graph.RemoveVertex(vertex1);
	group0.InsertNewVertex(vertex1);
	// Vertex2 can replace vertex1
	Vertex::CreateInterchangeableLink(vertex1,vertex2);
	// now put vertex1 back in the graph
	group0.RemoveVertex(vertex1);
	graph.InsertVertex(vertex1);

	// Now replace
	vertex1->Replace(&graph);

	// Make sure we left the vertices where they are supposed to be
	if (TestUtils::VerifyIsTrue(vertex1->IsInGraph(), "Vertex1 is supposed to be in graph but it doesn't think so") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(vertex1->GetContainer() != &group0, "Vertex1 thinks it is in group0") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(vertex2->GetContainer() == &group0, "Vertex2 doesn't think it is in the group") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(group0.IsVertexInGroup(vertex2->Name()), "Group0 doesn't contain vertex2") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	// check that the directory was updated correctly: All vertices in the graph appear in the graph. All vertices
	// in the group point to the right group.
	if (Algorithms::ValidateVertexDirectoryState(&graph, &group0) == false)
	{
		return TestUtils::TestFailed;
	}

	return TestUtils::TestPassed;

}


TestUtils::TestResult TestCouplesReplace()
{
	VertexDirectory::Clear();
	Graph graph(400);
	graph = TestUtils::CreateGraph4On2(graph);

	Group group0(0);
	bool name1[] = {0,1,1,0};
	bool name2[] = {1,0,0,1};
	bool name3[] = {1,0,1,0};
	bool name4[] = {0,1,0,1};
	int n = 4;
	Vertex *vertex1 = VertexDirectory::GetStaticCopyVertex(Vertex::GetNameFromArray(name1,n));
	Vertex *vertex2 = VertexDirectory::GetStaticCopyVertex(Vertex::GetNameFromArray(name2,n));
	Vertex *vertex3 = VertexDirectory::GetStaticCopyVertex(Vertex::GetNameFromArray(name3,n));
	Vertex *vertex4 = VertexDirectory::GetStaticCopyVertex(Vertex::GetNameFromArray(name4,n));
	
	VertexSet *set1 = new VertexSet(vertex1,vertex2);
	VertexSet *set2 = new VertexSet(vertex3,vertex4);
	
	graph.RemoveVertexSet(set1);

	group0.InsertNewVertexCouple(set1);
	
	// Vertex2 can replace vertex1
	VertexSet::CreateInterchangeableLink(set1,set2);
	// now put vertex1 back in the graph
	group0.RemoveVertexSet(set1);
	graph.InsertVertexSet(set1);

	VertexDirectory::AddVertexSet(set1);
	VertexDirectory::AddVertexSet(set2);

	// Make sure we left the vertices where they are supposed to be
	if (TestUtils::VerifyIsTrue(set1->CanBeReplaced(), "Vertexset1 can be replaced but it doesn't think so") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	// Make sure we left the vertices where they are supposed to be
	if (TestUtils::VerifyIsTrue(set2->CanAllRelatedInterchangeablesBeReplaced(), "Vertexset2 has a problem with related interchangeables") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}


	// Now replace
	set1->Replace(&graph);

	// Make sure we left the vertices where they are supposed to be
	if (TestUtils::VerifyIsTrue(set1->IsInGraph(), "Vertexset1 is supposed to be in graph but it doesn't think so") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(set1->Vertex1()->GetContainer() != &group0, "Vertexset1 thinks it is in group0") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}
	if (TestUtils::VerifyIsTrue(set1->Vertex2()->GetContainer() != &group0, "Vertexset1 thinks it is in group0") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(set2->Vertex1()->GetContainer() == &group0, "Vertexset2 doesn't think it is in the group") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}
	if (TestUtils::VerifyIsTrue(set2->Vertex2()->GetContainer() == &group0, "Vertexset2 doesn't think it is in the group") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	if (TestUtils::VerifyIsTrue(group0.IsVertexCoupleInGroup(set2), "Group0 doesn't contain vertexset2") == TestUtils::TestFailed)
	{
		return TestUtils::TestFailed;
	}

	// check that the directory was updated correctly: All vertices in the graph appear in the graph. All vertices
	// in the group point to the right group.
	if (Algorithms::ValidateVertexDirectoryState(&graph, &group0) == false)
	{
		return TestUtils::TestFailed;
	}

	return TestUtils::TestPassed;

}